LeetCode 21. Merge Two Sorted Lists

21. Merge Two Sorted Lists（合并两个有序链表）

链接

https://leetcode-cn.com/problems/merge-two-sorted-lists/

题目

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

思路

简单的链表题目，可以循环做，也可以递归做，这里采用的是递归。
如果结点为空，那么后面就不用继续判断，直接加到尾部即可，不然的话就需要比较两个结点的大小，小的加入，大的继续运算。

代码

public class ListNode {

  int val;
  ListNode next;

  ListNode(int x) {
    val = x;
  }
}


public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  if (l1 == null) {
    return l2;
  }
  if (l2 == null) {
    return l1;
  }
  if(l1.val<l2.val){
    l1.next=mergeTwoLists(l1.next,l2);
    return l1;
  }else {
    l2.next=mergeTwoLists(l1,l2.next);
    return l2;
  }
}